package structures.tree;

import java.util.Arrays;

public class HeapSortDemo {
    private static final int LENGTH = 10;

    public static void main(String[] args) {
        // 生成数据
        int[] data = new int[LENGTH];
        for (int index = 0; index < data.length; index++) {
            data[index] = (int) (Math.random() * LENGTH);
        }

        // 打印数据
        System.out.println(Arrays.toString(data));

        long startTime = System.currentTimeMillis();
        heapSort(data);
        System.out.println("----------------消耗时间: " + (System.currentTimeMillis() - startTime) + " ms------------");

        // 打印数据
        System.out.println(Arrays.toString(data));
    }

    /**
     * 堆排序
     *
     * @param data
     */
    private static void heapSort(int[] data) {
        // 构建大顶堆
        for (int i = data.length / 2 - 1; i >= 0; i--) {
            adjustHeap(data, i, data.length);
        }

        // 调整堆结构 + 交换头尾数据
        int temp = 0;
        for (int j = data.length - 1; j > 0; j--) {
            temp = data[j];
            data[j] = data[0];
            data[0] = temp;
            adjustHeap(data, 0, j);
        }
    }

    /**
     * 把数组调整为大顶堆(建立在大顶堆已构建的基础上)
     *
     * @param data   数据源
     * @param i      表示非叶子节点在数组中的索引
     * @param length 表示需要调整的数据长度   length在大顶堆排序中是在逐渐减少的
     */
    private static void adjustHeap(int[] data, int i, int length) {
        int temp = data[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && data[k] < data[k + 1]) {
                k++;
            }
            if (data[k] > temp) {
                // 把子节点的值赋给父节点(i也是会变得  i = k)
                data[i] = data[k];
                i = k;
            } else {
                break;
            }
        }
        data[i] = temp;
    }
}
